Q: Which of the following properties is associated with a queue?
A. First In Last Out
B. First In First Out
C. Last In First Out
D. Last In Last Out
Solution: Queue follows First In First Out structure.
Q: In a circular queue, how do you increment the rear end of the queue?
A. rear++
B. (rear+1) % CAPACITY
C. (rear % CAPACITY)+1
D. rear–
Solution: Ensures rear takes the values from 0 to (CAPACITY-1).
Q: What is the term for inserting into a full queue known as?
A. overflow
B. underflow
C. null pointer exception
D. program won’t be compiled
Solution: Just as stack, inserting into a full queue is termed overflow.
Q: What is the time complexity of enqueue operation?
A. O(logn)
B. O(nlogn)
C. O(n)
D. O(1)
Solution: Enqueue operation is at the rear end, it takes O(1) time to insert a new item into the queue.
Q: What does the following Java code do?
public Object function()
{
if(isEmpty())
return -999;
else
{
Object high;
high = q[front];
return high;
}
}
A. Dequeue
B. Enqueue
C. Return the front element
D. Return the last element
Solution: q[front] gives the element at the front of the queue, since we are not moving the ‘front’ to the next element,
it is not a dequeue operation.
Q: What is the need for a circular queue?
A. effective usage of memory
B. easier computations
C. to delete elements based on priority
D. implement LIFO principle in queues
Solution: In a linear queue, dequeue operation causes the starting elements of the array to be empty, and there is no way you can use that space, while in a circular queue, you can effectively use that space. Priority queue is used to delete the elements based on their priority. Higher priority elements will be deleted first whereas lower priority elements will be deleted next. Queue data structure always follows FIFO principle.
Q: Which of the following represents a dequeue operation? (count is the number of elements in the queue)
A. public Object dequeue()
{
if(count == 0)
{
System.out.println("Queue underflow");
return 0;
}
else
{
Object ele = q[front];
q[front] = null;
front = (front+1)%CAPACITY;
count--;
return ele;
}
}
B. public Object dequeue()
{
if(count == 0)
{
System.out.println("Queue underflow");
return 0;
}
else
{
Object ele = q[front];
front = (front+1)%CAPACITY;
q[front] = null;
count--;
return ele;
}
}
C. public Object dequeue()
{
if(count == 0)
{
System.out.println("Queue underflow");
return 0;
}
else
{
front = (front+1)%CAPACITY;
Object ele = q[front];
q[front] = null;
count--;
return ele;
}
}
D. public Object dequeue()
{
if(count == 0)
{
System.out.println("Queue underflow");
return 0;
}
else
{
Object ele = q[front];
q[front] = null;
front = (front+1)%CAPACITY;
return ele;
count--;
}
}
Solution: Dequeue removes the first element from the queue, ‘front’ points to the front end of the queue and returns the first element.
Q: Which of the following best describes the growth of a linear queue at runtime? (Q is the original queue, size() returns the number of elements in the queue)
A. private void expand()
{
int length = size();
int[] newQ = new int[length<<1];
for(int i=front; i<=rear; i++)
{
newQ[i-front] = Q[i%CAPACITY];
}
Q = newQ;
front = 0;
rear = size()-1;
}
B. private void expand()
{
int length = size();
int[] newQ = new int[length<<1];
for(int i=front; i<=rear; i++)
{
newQ[i-front] = Q[i%CAPACITY];
}
Q = newQ;
}
C. private void expand()
{
int length = size();
int[] newQ = new int[length<<1];
for(int i=front; i<=rear; i++)
{
newQ[i-front] = Q[i];
}
Q = newQ;
front = 0;
rear = size()-1;
}
D. private void expand()
{
int length = size();
int[] newQ = new int[length*2];
for(int i=front; i<=rear; i++)
{
newQ[i-front] = Q[i%CAPACITY];
}
Q = newQ;
}
Solution: A common technique to expand the size of array at run time is simply to double the size. Create a new array of double the previous size and copy all the elements, after copying do not forget to assign front = 0 and rear = size()-1, as these are necessary to maintain the decorum of the queue operations.
Q: What is the space complexity of a linear queue having n elements?
A. O(n)
B. O(nlogn)
C. O(logn)
D. O(1)
Solution: Because there are n elements.
Q: What is the output of the following Java code?
public class CircularQueue
{
protected static final int CAPACITY = 100;
protected int size,front,rear;
protected Object q[];
int count = 0;
public CircularQueue()
{
this(CAPACITY);
}
public CircularQueue (int n)
{
size = n;
front = 0;
rear = 0;
q = new Object[size];
}
public void enqueue(Object item)
{
if(count == size)
{
System.out.println("Queue overflow");
return;
}
else
{
q[rear] = item;
rear = (rear+1)%size;
count++;
}
}
public Object dequeue()
{
if(count == 0)
{
System.out.println("Queue underflow");
return 0;
}
else
{
Object ele = q[front];
q[front] = null;
front = (front+1)%size;
count--;
return ele;
}
}
public Object frontElement()
{
if(count == 0)
return -999;
else
{
Object high;
high = q[front];
return high;
}
}
public Object rearElement()
{
if(count == 0)
return -999;
else
{
Object low;
rear = (rear-1)%size;
low = q[rear];
rear = (rear+1)%size;
return low;
}
}
}
public class CircularQueueDemo
{
public static void main(String args[])
{
Object var;
CircularQueue myQ = new CircularQueue();
myQ.enqueue(10);
myQ.enqueue(3);
var = myQ.rearElement();
myQ.dequeue();
myQ.enqueue(6);
var = mQ.frontElement();
System.out.println(var+" "+var);
}
}
A. 3 3
B. 3 6
C. 6 6
D. 10 6
Solution: First enqueue 10 and 3 into the queue, followed by a dequeue(removes 10), followed by an enqueue(6), At this point, 3 is at the front end of the queue and 6 at the rear end, hence a call to frontElement() will return 3 which is displayed twice.